package chapter16;

import java.util.LinkedList;

/**
 * 贪心-01背包问题
 */
public class Pack {

    public static int max = Integer.MIN_VALUE;
    public static LinkedList<Integer> maxSelector = null;

    /**
     * 回溯法
     * <p>
     * 核心：
     * 0.收集选择项
     * 1.做选择
     * 2.递归
     * 3.回退
     */
    public static void zeroOnePack(int[] c, int[] w, int n, int k, LinkedList<Integer> selector) {
        int tn = n - c[k];
        if (tn <= 0) {
            int temp = 0;
            for (Integer s : selector) {
                temp += w[s];
            }
            if (temp > max) {
                max = temp;
                maxSelector = new LinkedList<>(selector);
            }
            return;
        }

        for (int i = 0; i <= 2; i++) {
            if (!selector.contains(k)) {
                selector.add(i);
            }
            zeroOnePack(c, w, tn, i, selector);
            if (!selector.isEmpty()) {
                selector.removeLast();
            }
        }
    }

    /**
     * 动态规划
     * <p>
     * 最优子结构：
     * max(当前空间已装入的价值,上一次装入空间的价值+待装入的价值)
     * <p>
     * 例如：
     * c=[0,10,20,30]
     * w=[0,60,100,120]
     * <p>
     * 转矩阵：
     * *        1 2 3 4 5 6 7 8 ... m (背包剩余空间)
     * * c  w
     * * 00 000
     * * 10 060
     * * 20 100
     * * 30 120
     */
    public static int zeroOnePack(int[] c, int[] w, int n, int m) {
        int[][] dp = new int[n + 1][m + 1];
        // 选择
        for (int i = 1; i <= n; i++) {
            // 背包容量
            for (int j = 1; j <= m; j++) {
                // j < c[i] 代表不够装入
                if (j < c[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    //dp[i - 1][j - c[i]]  [j - c[i]]代表上一次装入的价值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);
                }
            }
        }
        return dp[n][m];
    }

    /**
     * 贪心
     * <p>
     * 核心：按价值排序
     */
    public static int zeroOnePack2(int[] c, int[] w, int n) {
        int max = 0;
        for (int i = 0; i < c.length; i++) {
            // 当前已选的总价值
            int tm = 0;
            // 已占有的空间
            int tsc = 0;
            for (int j = i; j < w.length; j++) {
                // c[j] + tsc 当前选择的容量加已占用容量如果小于总背包容量就继续选择
                if (c[j] + tsc <= n) {
                    tsc += c[j];
                    tm += w[j];
                    max = Math.max(max, tm);
                }
            }
        }
        return max;
    }

    /**
     * 分数背包问题,可以看作能把背包填满的方法
     */
    public static double zeroOnePack3(int[] c, int[] w, int n) {
        double sum = 0;
        int tn = 0;
        for (int i = 0; i < c.length; i++) {
            if (tn + c[i] <= 50) {
                sum += w[i];
                tn += c[i];
            } else {
                sum += (double) w[i] / c[i] * (n - tn);
            }
        }
        return sum;
    }


}
